package Lee_code;

import java.util.*;

/**
 * @author blh
 * @date 2024年06月28日 10:05
 */
public class Lee_22_628 {
    List<String> res;
    HashSet<String> hashSet = new HashSet<>();
    int len;

    public List<String> generateParenthesis(int n) {
        len = n;
        // 应该是用回溯, leftNum记录使用的左括号数量
        traceBack(new StringBuilder(), 0);
        res = new ArrayList<>(hashSet);
        return res;
    }

    private void traceBack(StringBuilder list, int leftNum) {
        if (countLeft(list) == len) {
            // 有了n个left
            StringBuilder temp = new StringBuilder(list);
            int rightNum = list.length() - len;

            for (int i = 0; i < len - rightNum; i++) {
                temp.append(')');
            }
            String tempString = temp.toString();
            hashSet.add(tempString);
            return;
        }
        for (int i = leftNum; i < len; i++) {
            list.append('(');
            int tempNum = i+1;
            StringBuilder temp = new StringBuilder(list);
            int rightNum = list.length()-tempNum;
            for (int j=0; j<(tempNum - rightNum); j++){
                temp.append(')');
                traceBack(new StringBuilder(temp), tempNum);
            }
            traceBack(new StringBuilder(list), tempNum);
        }
    }

    private int countLeft(StringBuilder list) {
        int count=0;
        for (int i=0; i<list.length(); i++){
            if (list.charAt(i)=='('){
                count++;
            }
        }
        return count;
    }
}


